/**
 * @author hewei
 * @version 1.0
 * @description: 1039. 多边形三角剖分的最低得分
 * @date 2022/10/20 21:21
 */

public class MinScoreTriangulation {

    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                for (int k = i + 1; k < j; k++) {
                    int temp = values[i] * values[j] * values[k];
                    int min = Math.min(dp[i][j], temp + dp[i][k] + dp[k][j]);
                    dp[i][j] = min == 0 ? temp + dp[i][k] + dp[k][j] : min;
                }
            }
        }
        return dp[0][n - 1];
    }
}
